package treeedit;

import java.util.Arrays;
import java.util.Hashtable;

public class TedAlgorithm {
	private static int _del = 1;
	private static int _ins = 1;
	private static int _ren = 1;

	private static int[][] td;
	private static int[] l1, l2;
	private static int[] kr1, kr2;
	private static int[][] fd;
	private static Hashtable<Integer, Tree> hashId1;
	private static Hashtable<Integer, Tree> hashId2;

	public static int getDistance(Tree tree1, Tree tree2) {
		// Tree Id start from 1, so let arrays start from 1 too.
		int s1 = tree1.getSize();
		// System.out.println(s1);
		int s2 = tree2.getSize();

		td = new int[s1 + 1][s2 + 1];

		l1 = lmld(tree1);
		// Helper.printArray(l1, 1, s1);
		kr1 = getKeyRoot(l1, tree1.getLeavesSize());
		// Helper.printArray(kr1, 1, kr1.length-1);

		l2 = lmld(tree2);
		// Helper.printArray(l2, 1, s2);
		kr2 = getKeyRoot(l2, tree2.getLeavesSize());
		// Helper.printArray(kr2, 1, kr2.length-1);

		fd = new int[s1 + 1][s2 + 1];
		tree1.getHashId(hashId1 = new Hashtable<Integer, Tree>());
		tree2.getHashId(hashId2 = new Hashtable<Integer, Tree>());

		for (int i = 1; i < kr1.length; i++)
			for (int j = 1; j < kr2.length; j++)
				forest_dist(kr1[i], kr2[j]);

		return td[s1][s2];
	}

	/**
	 * Fill the array with leftmost leaf descendants.
	 * 
	 * @param tree
	 *            Tree to get the array of LMLD for
	 */
	public static int[] lmld(Tree tree) {
		int[] arrayOfDescendants = new int[tree.getSize() + 1];
		lmld(tree, arrayOfDescendants);
		return arrayOfDescendants;
	}

	private static void lmld(Tree tree, int[] arrayOfDescendants) {
		if (tree.isLeaf())
			arrayOfDescendants[tree.getId()] = tree.getId();
		else {
			for (Tree c : tree.getChildren())
				lmld(c, arrayOfDescendants);
			arrayOfDescendants[tree.getId()] = arrayOfDescendants[tree.getFirstChild()
					.getId()];
		}
	}

	public static int[] getKeyRoot(int[] lmldArray, int leafCount) {

		int[] kr = new int[leafCount + 1];
		boolean[] visited = new boolean[lmldArray.length];
		Arrays.fill(visited, false);

		int k = kr.length - 1;
		int i = lmldArray.length - 1;
		while (k >= 1) {
			if (!visited[lmldArray[i]]) {
				kr[k--] = i;
				visited[lmldArray[i]] = true;
			}
			i--;
		}
		Arrays.sort(kr, 1, kr.length - 1);
		return kr;
	}

	private static int rename_cost(int i, int j) {
		Tree t1 = hashId1.get(i);
		Tree t2 = hashId2.get(j);
		if (t1.getName().equals(t2.getName()))
			return 0;
		return _ren;
	}

	private static void forest_dist(int i, int j) {
		fd[l1[i] - 1][l2[j] - 1] = 0;

		for (int di = l1[i]; di <= i; di++)
			fd[di][l2[j] - 1] = fd[di - 1][l2[j] - 1] + _del;

		for (int dj = l2[j]; dj <= j; dj++)
			fd[l1[i] - 1][dj] = fd[l1[i] - 1][dj - 1] + _ins;

		for (int di = l1[i]; di <= i; di++)
			for (int dj = l2[j]; dj <= j; dj++)
				if (l1[di] == l1[i] && l2[dj] == l2[j]) {
					fd[di][dj] = Math.min(
							Math.min(fd[di - 1][dj] + _del, fd[di][dj - 1] + _ins),
							fd[di - 1][dj - 1] + rename_cost(di, dj));
					td[di][dj] = fd[di][dj];
				} else {
					fd[di][dj] = Math.min(
							Math.min(fd[di - 1][dj] + _del, fd[di][dj - 1] + _ins),
							fd[l1[di] - 1][l2[dj] - 1] + td[di][dj]);
				}
	}
}
